package pl.com.qapps.util;

import java.lang.reflect.Array;
import java.util.AbstractList;
import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * This class is NotThreadSafe.<br>
 * <br>
 * When creating sublist, it is safe to add elements to parent list, the changes
 * will be reflected in sublist, but remove operations on parent list does not
 * guarantee this (actually it guaranteed but not for elements: before first and
 * after last in sublist). So every add operation is fully safe and will be
 * reflected in all sublists.
 * 
 * @author Jakub Dykowski
 * 
 */
public class LinkList<E> extends AbstractList<E> implements List<E>, Queue<E>,
		Deque<E> {

	private Element first;
	private Element last;

	private final Element start;
	private final Element end;

	// private int modCount;

	private LinkList<E> parent;

	public LinkList() {
		this(null, null);
	}

	public LinkList(Collection<? extends E> source) {
		this(null, null);
		addAll(source);
	}

	private LinkList(Element start, Element end) {
		this.start = start;
		this.end = end;
		this.first = end;
		this.last = start;
	}

	@Override
	public boolean add(E item) {
		new Element(last, item, end);
		return true;
	}

	@Override
	public void add(int index, E item) {
		try {
			Element e = first;
			for (int i = 0; i < index; i++)
				e = e.next;
			new Element(e.prev, item, e);
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public boolean addAll(Collection<? extends E> c) {
//		if (c instanceof RandomAccess) {
			for (E item : c)
				new Element(last, item, end);
			// Object[] array = c.toArray();
			// for (Object o : array) {
			// new Element(last, (E) o, end);
			// }
			 return true;
//		}

//		Iterator<? extends E> iter = c.iterator();
//		Element e;
//		Element next;
//		if (iter.hasNext()) {
//			e = new Element(last, iter.next(), end);
//			while (iter.hasNext()) {
//				next = new Element(iter.next());
//				e.next = next;
//				next.prev = e;
//				e = next;
//			}
//			link(e, end);
//			return true;
//		}
//		return false;
	}

	@Override
	public boolean addAll(int index, Collection<? extends E> c) {
		try {
			Element before = first;
			for (int i = 0; i < index; i++)
				before = before.next;
			return new LinkList<E>(before.prev, before).addAll(c);
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public void clear() {
		link(start, end);
	}

	@Override
	public boolean contains(Object o) {
		return indexOf(o) >= 0;
	}

	@Override
	public boolean containsAll(Collection<?> c) {
		for (Object o : c)
			if (!contains(o))
				return false;
		return true;
	}

	@Override
	public E get(int index) {
		try {
			Element e = first;
			for (int i = 0; i < index; i++)
				e = e.next;
			return e.item;
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public int indexOf(Object o) {
		int i = 0;
		for (Element e = first; e != end; e = e.next, i++)
			if (e.item.equals(o))
				return i;
		return -1;
	}

	@Override
	public boolean isEmpty() {
		return first != end;
	}

	@Override
	public Iterator<E> iterator() {
		return new Iterator<E>() {

			Element current = new Element(first);
			boolean canDelete;

			@Override
			public boolean hasNext() {
				return current.next != end;
			}

			@Override
			public E next() {
				if (!hasNext()) {
					canDelete = false;
					throw new NoSuchElementException();
				}
				current = current.next;
				canDelete = true;
				return current.item;
			}

			@Override
			public void remove() {
				if (!canDelete)
					throw new IllegalStateException();
				link(current.prev, current.next);
				canDelete = false;
			}

		};
	}

	@Override
	public int lastIndexOf(Object o) {
		int i = size() - 1;
		for (Element e = last; e != start; e = e.prev, i--)
			if (e.item.equals(o))
				return i;
		return -1;
	}

	@Override
	public ListIterator<E> listIterator() {
		return new ListIterator<E>() {

			Element current = new Element(first);
			int pos = 0;
			boolean canModify;

			@Override
			public void add(E item) {
				new Element(current.prev, item, current);
				canModify = false;
				++pos;
			}

			@Override
			public boolean hasNext() {
				return current.next != end;
			}

			@Override
			public boolean hasPrevious() {
				return current.prev != start;
			}

			@Override
			public E next() {
				if (current.next == end) {
					canModify = false;
					throw new NoSuchElementException();
				}
				current = current.next;
				++pos;
				canModify = true;
				return current.item;
			}

			@Override
			public int nextIndex() {
				return pos + 1;
			}

			@Override
			public E previous() {
				if (current.prev != start) {
					canModify = false;
					throw new NoSuchElementException();
				}
				current = current.prev;
				canModify = true;
				--pos;
				return current.item;
			}

			@Override
			public int previousIndex() {
				return pos - 1;
			}

			@Override
			public void remove() {
				if (!canModify)
					throw new IllegalStateException();
				link(current.prev, current.next);
				canModify = false;
				--pos;
			}

			@Override
			public void set(E item) {
				if (!canModify)
					throw new IllegalStateException();
				current.item = item;
			}

		};
	}

	@Override
	public ListIterator<E> listIterator(int index) {
		try {
			Element from = first;
			for (int i = 0; i < index; i++)
				from = from.next;
			return new LinkList<E>(from.prev, end).listIterator();
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public boolean remove(Object o) {
		for (Element e = first; e != end; e = e.next)
			if (e.item.equals(o)) {
				link(e.prev, e.next);
				return true;
			}
		return false;
	}

	@Override
	public E remove(int index) {
		try {
			Element e = first;
			for (int i = 0; i < index; i++)
				e = e.next;
			link(e.prev, e.next);
			return e.item;
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public boolean removeAll(Collection<?> c) {
		boolean result = false;
		for (Object o : c)
			result |= remove(o);
		return result;
	}

	@Override
	public boolean retainAll(Collection<?> c) {
		if (c == null)
			throw new NullPointerException("Collection cannot be null");
		boolean changed = false;
		loop: for (Element e = first; e != end; e = e.next) {
			for (Object other : c) {
				if (other.equals(e.item))
					continue loop;
			}
			link(e.prev, e.next);
			changed = true;
		}
		return changed;
	}

	@Override
	public E set(int index, E item) {
		try {
			Element e = first;
			for (int i = 0; i < index; i++)
				e = e.next;
			E previous = e.item;
			e.item = item;
			return previous;
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public int size() {
		if (first == end)
			return 0;
		Element e = first;
		int count = 0;
		do {
			++count;
			e = e.next;
		} while (e != end);
		return count;
	}

	@Override
	public List<E> subList(int fromIndex, int toIndex) {
		if (toIndex > fromIndex)
			throw new IndexOutOfBoundsException();
		try {
			int i = 0;
			Element from = first;
			for (; i < fromIndex; i++)
				from = from.next;
			Element to = from;
			for (; i < toIndex; i++)
				to = to.next;
			return new LinkList<E>(from.prev, to.next);
		} catch (NullPointerException e) {
			throw new IndexOutOfBoundsException();
		}
	}

	@Override
	public Object[] toArray() {
		Object[] array = new Object[size()];
		int i = 0;
		for (Element e = first; e != end; e = e.next, i++)
			array[i] = e.item;
		return array;
	}

	@SuppressWarnings("unchecked")
	@Override
	public <T extends Object> T[] toArray(T[] array) {
		if (array == null)
			throw new NullPointerException();
		int i = 0;
		int size = size();
		if (array.length >= size) {
			for (Element element = first; element != end; element = element.next) {
				array[i++] = (T) element.item;
			}
			return array;
		} else {
			T[] items = (T[]) Array.newInstance(array.getClass(), size);
			try {
				for (Element element = first; element != end; element = element.next) {
					items[i++] = (T) element.item;
				}
			} catch (ClassCastException e) {
				throw new ArrayStoreException();
			}
			return (T[]) items;
		}
	}

	private class Element {

		Element prev;
		Element next;
		E item;

		Element(E item) {
			this.item = item;
		}

		Element(Element prev, E item) {
			this.prev = prev;
			this.item = item;
		}

		Element(Element next) {
			this.next = next;
		}

		Element(Element prev, E item, Element next) {
			this.item = item;
			this.prev = prev;
			if (prev != start) {
				prev.next = this;
			} else {
				// link first
				if (parent != null)
					parent.linkFirst(this);
				first = this;
			}
			this.next = next;
			if (next != end) {
				next.prev = this;
			} else {
				// link last
				if (parent != null)
					parent.linkLast(this);
				last = this;
			}
		}
	}

	private void link(Element one, Element another) {
		if (one != null)
			one.next = another;
		if (one == start) {
			// link one as first
			if (parent != null)
				parent.linkFirst(another);
			first = another;
		}
		if (another != null)
			another.prev = one;
		if (another == end) {
			// link another as last
			if (parent != null)
				parent.linkLast(one);
			last = one;
		}
	}

	private void linkFirst(Element element) {
		if (parent != null)
			parent.linkFirst(element);
		first = element;
	}

	private void linkLast(Element element) {
		if (parent != null)
			parent.linkLast(element);
		last = element;
	}

	@Override
	public E element() {
		if (first == end)
			throw new NoSuchElementException();
		return first.item;
	}

	@Override
	public boolean offer(E item) {
		new Element(last, item, end);
		return true;
	}

	@Override
	public E peek() {
		return first != end ? first.item : null;
	}

	@Override
	public E poll() {
		if (first == end)
			return null;
		E item = first.item;
		link(start, first.next);
		return item;
	}

	@Override
	public E remove() {
		if (first == end)
			throw new NoSuchElementException();
		E item = first.item;
		link(start, first.next);
		return item;
	}

	@Override
	public void addFirst(E item) {
		new Element(start, item, first);
	}

	@Override
	public void addLast(E item) {
		new Element(last, item, end);
	}

	@Override
	public Iterator<E> descendingIterator() {
		return new Iterator<E>() {

			Element current = new Element(last, null);
			boolean canDelete = false;

			@Override
			public boolean hasNext() {
				return current.prev != start;
			}

			@Override
			public E next() {
				if (!hasNext()) {
					canDelete = false;
					throw new NoSuchElementException();
				}
				current = current.prev;
				canDelete = true;
				return current.item;
			}

			@Override
			public void remove() {
				if (!canDelete)
					throw new IllegalStateException();
				link(current.prev, current.next);
				canDelete = false;
			}

		};
	}

	@Override
	public E getFirst() {
		if (first == end)
			throw new NoSuchElementException();
		return first.item;
	}

	@Override
	public E getLast() {
		if (last == start)
			throw new NoSuchElementException();
		return last.item;
	}

	@Override
	public boolean offerFirst(E item) {
		new Element(start, item, first);
		return true;
	}

	@Override
	public boolean offerLast(E item) {
		new Element(last, item, end);
		return true;
	}

	@Override
	public E peekFirst() {
		return first == end ? null : first.item;
	}

	@Override
	public E peekLast() {
		return last == start ? null : last.item;
	}

	@Override
	public E pollFirst() {
		if (first == end)
			return null;
		E item = first.item;
		link(start, first.next);
		return item;
	}

	@Override
	public E pollLast() {
		if (last == start)
			return null;
		E item = last.item;
		link(last.prev, end);
		return item;
	}

	@Override
	public E pop() {
		if (first == end)
			throw new NoSuchElementException();
		E item = first.item;
		link(start, first.next);
		return item;
	}

	@Override
	public void push(E item) {
		new Element(start, item, first);
	}

	@Override
	public E removeFirst() {
		if (first == end)
			throw new NoSuchElementException();
		E item = first.item;
		link(start, first.next);
		return item;
	}

	@Override
	public boolean removeFirstOccurrence(Object o) {
		return remove(o);
	}

	@Override
	public E removeLast() {
		if (last == start)
			throw new NoSuchElementException();
		E item = last.item;
		link(last.prev, end);
		return item;
	}

	@Override
	public boolean removeLastOccurrence(Object arg0) {
		for (Element e = last; e != start; e = e.prev)
			if (e.item.equals(arg0)) {
				link(e.prev, e.next);
				return true;
			}
		return false;
	}

}
